import java.util.*;

public class project {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer,Integer> map=new HashMap<>();
        for(List<Integer> list:wall){
            int len=list.size();
            int sum=0;
            for(int i=0;i<len-1;i++){
                sum+=list.get(i);
                map.put(sum,map.getOrDefault(sum,0)+1);
            }
        }
        int max=0;
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            max=Math.max(max,entry.getValue());
        }
        return wall.size()-max;
    }















    public List<String> findRepeatedDnaSequences(String s) {
        List<String> list=new ArrayList<>();
        Map<String,Integer> map=new HashMap<>();
        for(int i=0;i<=s.length()-10;i++){
            String str=s.substring(i,i+10);
            map.put(str,map.getOrDefault(str,0)+1);
            if(map.get(str)==2){
                list.add(str);
            }
        }
        return list;
    }



















    public static void main(String[] args) {
        String s="leetcode";
        List<String> word=new ArrayList<>();
        word.add("leet");
        word.add("code");
        System.out.println(wordBreak(s,word));
    }
    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set=new HashSet<>();
        for(String value:wordDict){
            set.add(value);
        }
        boolean[] dp=new boolean[s.length()+1];
        dp[0]=true;
        for(int i=1;i<=s.length();i++){
            for(int j=0;j<i;j++){
                if(dp[j]&& set.contains(s.substring(j,i))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }




















    public int longestSubstring(String s, int k) {
        if(s.length()<k){
            return 0;
        }

        Map<Character,Integer> map=new HashMap<>();
        for(char ch:s.toCharArray()){
            map.put(ch,map.getOrDefault(ch,0)+1);
        }

        for(char ch:map.keySet()){
            if(map.get(ch)<k){
                int max=0;
                String[] str=s.split(String.valueOf(ch));
                for(String newS:str){
                    max=Math.max(max,longestSubstring(newS,k));
                }
                return max;
            }
        }
        return s.length();
    }
















    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> list=new ArrayList<>();
        int index=left;
        while (index<=right){
            if(test(index)){
                list.add(index);
            }
            index++;
        }
        return list;
    }
    public boolean test(int index){
        int tmp=index;
        while (tmp!=0){
            int cur=tmp%10;
            if(cur==0||index%cur!=0){
                return false;
            }
            tmp/=10;
        }
        return true;
    }
}
